#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
void add(int **arr, int a, int b, int c)
{
    arr[a - 1][b - 1] = c;
}

int main()
{
    int n, m; // n是顶点数(有编号为1到n的n个顶点),m是变数
    scanf("%d%d", &n, &m);
    // 定义邻接矩阵,并对矩阵进行初始化
    int **adjMatrix = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++)
    {
        adjMatrix[i] = (int *)malloc(sizeof(int) * n);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            adjMatrix[i][j] = INT_MAX / 2;
        }
    }
    // 对邻接矩阵进行赋值,输入a,b,c分别表示从编号为a的点到编号为b的点距离为c
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(adjMatrix, a, b, c);
    }
    // 定义一个visited数组用来标记已经处理过的点,处理过为1,没处理过为0
    int *visited = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
    }
    // 定义一个dist数组用来表示起始结点到各个结点的最短路径,初始设置为INT_MAX/2;除以2的原因是防止min + adjMatrix[index][i]益出
    int *dist = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
    {
        dist[i] = INT_MAX / 2;
    }
    // 输入起始的顶点编号origin_vertex
    int origin_vertex;
    scanf("%d", &origin_vertex);
    dist[origin_vertex - 1] = 0;

    // 在dist数组中找到一个值最小的顶点,将这个顶点标记为已处理(要处理n次),然后更新dist数组
    int k = 0;
    int index; // 用于标记dist数组中未处理数值最小结点的数组索引
    int min;   // min为dist数组中未处理的最小值
    while (k++ < n)
    {
        min = INT_MAX / 2;
        index = -1;
        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && dist[i] < min)
            {

                index = i;
                min = dist[i];
            }
        }
        if (index == -1)
        {
            break;
        }
        visited[index] = 1;
        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && dist[i] > (min + adjMatrix[index][i]))
            {
                dist[i] = min + adjMatrix[index][i];
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (dist[i] == INT_MAX / 2)
        {
            printf("起始顶点%d到顶点%d没有最短路径\n", origin_vertex, i + 1);
        }
        printf("起始顶点%d到顶点%d的最短路径为%d\n", origin_vertex, i + 1, dist[i]);
    }
    for (int i = 0; i < n; i++)
    {
        free(adjMatrix[i]);
    }
    free(adjMatrix);
    free(visited);
    free(dist);
    return 0;
}